package com.fe.class03;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

/**
 * @Description 实现最小栈
 * @Author sosuke :-)
 * @Date 2021/12/12 05:26
 */
public class Code07_GetMinStack {

    /**
     * 实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
     * <p>
     * 1）pop、push、getMin操作的时间复杂度都是 O(1)。
     * 2）设计的栈类型可以使用现成的栈结构。
     */
    public static class MyMinStack1 {
        private Stack<Integer> dataStack;
        private Stack<Integer> minStack;

        public MyMinStack1() {
            this.dataStack = new Stack<>();
            this.minStack = new Stack<>();
        }

        // 入栈的数据小于等于minStack，则入栈minStack
        public void push(int data) {
            if (minStack.isEmpty() || data <= minStack.peek()) {
                minStack.push(data);
            }
            dataStack.push(data);
        }

        public int pop() {
            if (dataStack.isEmpty()) {
                throw new RuntimeException("栈空了，不能再取了");
            }
            int value = dataStack.pop();
            if (value == minStack.peek()) {
                minStack.pop();
            }
            return value;
        }

        public int getMin() {
            if (minStack.isEmpty()) {
                throw new RuntimeException("栈空了，没有最小值");
            }
            return minStack.peek();
        }

    }

    public static class MyMinStack2 {
        private Stack<Integer> dataStack;
        private Stack<Integer> minStack;

        public MyMinStack2() {
            this.dataStack = new Stack<>();
            this.minStack = new Stack<>();
        }

        // 入栈的数据大于minStack时，则入栈minStack的栈顶元素
        public void push(int data) {
            if (minStack.isEmpty() || data <= minStack.peek()) {
                minStack.push(data);
            } else {
                int newMin = minStack.peek();
                minStack.push(newMin);
            }
            dataStack.push(data);
        }

        // dataStack和minStack一样大小，只是minStack每层保存的都是对应的最小值
        public int pop() {
            if (dataStack.isEmpty()) {
                throw new RuntimeException("栈空了，不能再取了");
            }
            int value = dataStack.pop();
            minStack.pop();
            return value;
        }

        public int getMin() {
            if (minStack.isEmpty()) {
                throw new RuntimeException("栈空了，没有最小值");
            }
            return minStack.peek();
        }
    }

    public static void main(String[] args) {
        int testTimes = 10000;
        int maxValue = 200;
        int oneTestNums = 100;
        for (int i = 0; i < testTimes; i++) {
            MyMinStack1 myMinStack1 = new MyMinStack1();
            Stack<Integer> stack = new Stack<>();
            for (int j = 0; j < oneTestNums; j++) {
                int numStack = (int) (Math.random() * (maxValue + 1));
                if (stack.isEmpty()) {
                    stack.push(numStack);
                    myMinStack1.push(numStack);
                } else {
                    if (Math.random() < 0.5) {
                        stack.push(numStack);
                        myMinStack1.push(numStack);
                    } else {
                        stack.pop();
                        myMinStack1.pop();
                    }
                }
                // 使用stream获取最小值，两种方式比对
                if (!stack.isEmpty() && !isEqual(myMinStack1.getMin(), stack.stream().min(Comparator.comparingInt(a -> a)).get())) {
                    System.out.println("MyMinStack oops");
                }
            }
        }
        System.out.println("Nice");
    }

    private static boolean isEqual(Integer o1, Integer o2) {
        if (null == o1 && null != o2) return false;
        if (null != o1 && null == o2) return false;
        if (null == o1) return true;
        List<Integer> list = new ArrayList<>();
        list.sort(Integer::compareTo);
        return o1.equals(o2);
    }

}
